The problem of global optimization in multi-dimensional, highly nonlinear systems is a difficult and challenging task. The objective function may exhibit many local optima whereas the global optimum is sought. A solution to the optimization problem may be obtained that is less satisfactory than another solution elsewhere in the region. The better solution may be reached by initiating the search for the optimum from a starting point closer to the global optimum.
Representing and utilizing knowledge for design synthesis is a type of global optimization problem. In some domains, structured design synthesis techniques can generate designs automatically from functional specifications. But in many domains, these techniques are not practical and/or possible. For example, mechanical devices may have equations of motion that are complex, highly nonlinear, and difficult to comprehend, thwarting structured design methodologies. In such domains, a designer often proceeds by building and/or simulating devices, analyzing these designs, and gaining intuition about the device behavior over the course of many design modifications.
1. Mechanical Linkages
Mechanical linkages are collections of rigid bodies connected by joints that allow restricted relative movement. They are found in a variety of everyday objects. Some examples are: the hinge for an automobile hood, an automobile suspension, aircraft landing gear, cranes, and bicycle derailleurs. The general problem is described in U.S. Pat. No. 5,043,929 (incorporated by reference).
The simplest mechanical linkage is the four-bar, planar linkage shown in FIG. 3. One link, called ground, serves as the reference frame for describing all relative movement. The other three links are called the crank, coupler, and follower. The crank and follower are attached to the ground link, and rotate about it on revolute joints. The other ends of the crank and follower are constrained to move relative to each other via the coupler link, which is the source of the nonlinearity in the four-bar's behavior. The tracer point is a point rigidly attached to the coupler. The path in space traced by the tracer point is called the coupler curve. These are closed curves; FIG. 3 shows only a portion of the coupler curve. FIG. 4 illustrates a coupler curve.
Linkages are used for three main purposes: path, motion, and function generation. See, Sandor, G. N. and A. G. Erdman. Advanced Mechanism Design: Analysis and Synthesis, Volume 2, Prentice-Hall, Inc., Englewood Cliffs, N.J. (1984). In path generation, the linkage is used to guide an object through space; no attention is given to the object's orientation. Motion generation is similar to path generation, but the orientation of the object is also controlled. In function generation, the nonlinear behavior of the linkage is utilized to approximate a desired functional relationship between the input and output cranks of the mechanism.
Analytic methods for linkage synthesis are based on the work of Burmester, see, Burmester, L. Lehrbuch tier Kinematic. A. Felix, Leipzig (1888), which involved graphical analysis of finite displacements of rigid-body planar linkages. This work, which handles a subset of purely analytic, exactly-constrained design problems, was later analyzed in the context of algebraic geometry and translated into computer programs. See, Erdman, A. G. Computer-aided design of mechanisms: 1984 and beyond. Mechanism and Machine Theory, 20:4,245-249 (1985).
Some techniques have been developed to handle overconstrained synthesis problems. Chebychev polynomials were developed specifically for kinematic synthesis and provide a good approximate fit to the overconstrained problem. See, Sarkisyan, Y. L., Gupta, K. C. and B. Roth. Chebychev approximations of finite point sets with application to planar kinematic synthesis. Journal of Mechanical Design, Trans. ASME, 101:1.32-40 (January 1979). A similar least-squares approach is found in Sutherland, G. H. and B. Roth. An improved least-squares method for designing function-generating mechanisms. Journal of Engineering for Industry, Trans. ASME Ser. B, 97:1,303-307 (February 1975).
Because of the limitations of algorithmic design methodologies, iterative design is commonplace among practicing engineers. Iterative synthesis describes a process in which the design is analyzed to determine how well it meets the design specification. If the behavior matches specification well enough, the design is complete; otherwise, some design variables (dimensions) are modified in order to make the behavior more closely match the specification, and the process is repeated. This style of design relies heavily upon the designer's experience, particularly in the initial selection of a mechanism.
Choosing design parameters requires an inverse model of behavior of the device; when such models are unavailable, designers must rely on experience. One way for a designer to overcome a lack of experience is to make use of past similar designs, by choosing a mechanism from a catalog. See, Artobolevsky, I. Mechanisms in Modern Engineering Design. USSR Academy of Sciences, Moscow, (1947-1952). Translated and reprinted by Mir Publishers, Moscow (1975). In the microcosm of four-bar linkages, the Hrones and Nelson atlas of four-bar coupler curves provides over 7300 different examples of four-bar crank and rocker mechanisms, along with guidelines for analysis and for synthesis of more complex linkages built upon the four-bar. See, Hrones, J. A. and G. L. Nelson. Analysis of the Four-bar Linkage. The Technology Press of MIT and John Wiley & Sons, Inc., New York (1951). However, finding an appropriate coupler curve in the catalog can be difficult.
The utility of design catalogs in the synthesis of linkages can be improved by automating the process of searching the catalog and retrieving appropriate past designs. Once such technique is described in Kramer, G. A. and H. G. Barrow. A case-based approach to the design of mechanical linkages. In Artificial Intelligence in Engineering Design, 2, 443-466, Academic Press, San Diego, Calif. (1992) and U.S. Pat. No. 5,043,929. However, the size of the catalog can be very large, and automated search is time-consuming. Furthermore, no interpolation between catalog entries is done.
2. Artificial Neural Networks
A great deal of recent research has been published relating to the application of artificial neural networks in a variety of contexts. See, for example, U.S. Pat. Nos. 5,134,685, 5,129,040, 5,113,483, and 5,107,442 (incorporated by reference). Artificial neural networks are computational models inspired by the architecture of the human brain. As a result three constraints are usually imposed on these models. The computations must be performed in parallel, the representation must be distributed, and the adjustment of network parameters (i.e., learning) must be adaptive. From an engineering perspective ANNs are adaptive, model-free estimators that estimate numerical functions using example data. While many different types of artificial neural networks exist, two common types are radial basis function (RBF) and back propagation artificial neural networks.
Radial basis function ANNs have the capability to synthesize an approximation to a multivariant function (or its inverse) by using a representative set of examples characteristic of the functions input-output mapping.
RBF ANNs are single hidden-layer, feedforward networks that use radially-symmetric basis functions as the activation functions for nodes in the hidden layer. The approximation learned by the RBF ANN is given by ##EQU1## where R.sub.j is a radially-symmetric basis function, x is the input vector, and w.sub.kj is the weight connecting the jth hidden node to the kth output node.
Typically, the basis function R for node j is the Gaussian function with unit normalization: ##EQU2## Equation (2) indicates that the output for node j peaks with a value of unity when the input vector equals the mean vector, x.sub.j, and falls off monotonically as the Euclidean norm between input and the mean vector of a node increases. .sigma..sub.j, the width of the response field of the basis function, determines the rate of decay of the Gaussian function R.
The nonpatent references cited herein are incorporated by reference for background.